/**
 *
 */
package offer.algorithm;

import java.util.Random;

/**
 * @author zhang 整型数组连续子序列的最大和
 */
public class LargeMaxSubSeq31 {

    //此函数 算法有误，待改正
    public static int lageMaxsubArr(int[] array) {
        int max = array[ 0 ], currentMax = array[ 0 ];
        for (int i = 1; i < array.length; i++) {
            if (array[ i ] > max)
                max = array[ i ];
            if (array[ i ] > 0) {
                currentMax += array[ i ];
                if (currentMax > max)
                    max = currentMax;
            } else {
                if (currentMax != 0 && currentMax > max)
                    max = currentMax;
                currentMax = currentMax + array[ i ] < 0 ? 0 : currentMax + array[ i ];
            }
        }
        return max;
    }

    private static int largeMax(int[] array) {

        int sum = 0;
        int max_sum = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            sum = sum + array[ i ];
            if (sum > max_sum) {
                max_sum = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
        }
        return max_sum;
    }

    private static int largeMaxOfSubArray(int[] array) {
        if (array == null || array.length <= 0)
            return Integer.MIN_VALUE;
        int len = array.length;
        int[] start = new int[ len ];
        int[] all = new int[ len ];
        start[ len - 1 ] = array[ len - 1 ];
        all[ len - 1 ] = array[ len - 1 ];
        for (int i = array.length - 2; i >= 0; i--) {
            start[ i ] = start[ i + 1 ] > 0 ? array[ i ] + start[ i + 1 ] : array[ i ];
            all[ i ] = start[ i ] > all[ i + 1 ] ? start[ i ] : all[ i + 1 ];
        }
        return all[ 0 ];
    }


    public static void main(String[] args) {
        Random random = new Random();
        for (int k = 0; k < 100; k++) {

            int len = random.nextInt(100) + 50;
            int[] ints = new int[ len ];
            for (int i = 0; i < len; i++) {
                ints[ i ] = random.nextInt(60) - 30;
            }
            int result1 = largeMax(ints);
            int result2 = largeMaxOfSubArray(ints);
            int result3 = lageMaxsubArr(ints);
            if (result1 == result2 && result1 == result3)
                System.out.print("");
            else
                System.out.println("What a fuck day!!!");
        }
    }

}
